package pers.vic.basics.leetcode;

/**
 * @description: 50. Pow(x, n) {@literal https://leetcode-cn.com/problems/powx-n/} 分治
 * @author Vic.xu
 * @date: 2020/12/11 0011 8:55
 */
public class J0050_M_MyPow {
    /*
    实现 pow(x, n) ，即计算 x 的 n 次幂函数。
    说明:
    -100.0 < x < 100.0
    n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
     */

    /**
     * 1. 不想判断int边界问题，直接转换为long了
     * 2. pow(x,n) == pow(x,n/2)* pow(x,n/2)[*x]   分治算法
     */
    public static double myPow(double x, int n) {
        long num = Math.abs((long)n);
        double res = pow(x, num);
        return n >= 0 ? res : 1.0 / res;
    }

    private static double pow(double x, long n) {
        double res = 1.0;
        //先把偶数个x相乘
        double xx = x;
        while (n > 0) {
            //
            if (n % 2 == 1) {
                res *= xx;
            }
            xx *= xx;
            n /= 2;
        }
        return res;
    }

    public static void main(String[] args) {

        System.out.println(myPow(2.0000, 10) + "   -> 1024.00000");
        System.out.println(myPow(2.1000, 3) + "   -> 9.26100");
        System.out.println(myPow(2.00000, -2) + "   -> 0.25");
        System.out.println(myPow(0.00001, 2147483647) + "   -> 0....");
        System.out.println(myPow(2.00000, -2147483648) + "   -> 0");

        //2.00000
        //-2147483648

    }
}
